
/**
 * 归并排序，是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
 * 
 */
public class MergeSort {

    // public int[] sortArray(int[] nums) {
    //     return merge(nums, 0, nums.length -1);
    // }

    // private int[] merge(int[] nums, int left, int right) {
    //     if (left < right) {
    //         int mid = left + (right -left) / 2;
    //         merge(nums, left, mid);
    //         merge(nums, mid + 1, right);
    //         sort(nums, left, mid, right);
    //     }
    //     return nums;
    // }

    // private void sort(int[] nums, int left, int mid, int right) {
    //     int[] temp = new int[nums.length];
    //     int i = left, j = mid + 1, k = 0;
    //     while (i <= mid && j <= right) {
    //         if (nums[i] < nums[j]) {
    //             temp[k++] = nums[i++];
    //         } else {
    //             temp[k++] = nums[j++];
    //         }
    //     }
    //     while (i <= mid) temp[k++] = nums[i++];
    //     while (j <= right) temp[k++] = nums[j++];
    //     for (i = 0; i < k; i++) {
    //         nums[i + left] = temp[i];
    //     }
    // }

    // 归并排序（Java-迭代版）
    // public static void main(String[] args){
    //     int[] arr = {49,38,65,97,76,13,27,49,78,34,12,64,1};
    //     int len = arr.length;
    //     int[] result = new int[len];
    //     int block, start;
        
    //     // 原版代码的迭代次数少了一次，没有考虑到奇数列数组的情况
    //     for(block = 1; block < len*2; block *= 2) {
    //         for(start = 0; start <len; start += 2 * block) {
    //             int low = start;
    //             int mid = (start + block) < len ? (start + block) : len;
    //             int high = (start + 2 * block) < len ? (start + 2 * block) : len;
    //             //两个块的起始下标及结束下标
    //             int start1 = low, end1 = mid;
    //             int start2 = mid, end2 = high;
    //             //开始对两个block进行归并排序
    //             while (start1 < end1 && start2 < end2) {
    //             result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    //             }
    //             while(start1 < end1) {
    //             result[low++] = arr[start1++];
    //             }
    //             while(start2 < end2) {
    //             result[low++] = arr[start2++];
    //             }
    //         }
    //     int[] temp = arr;
    //     arr = result;
    //     result = temp;
    //     }
    //     result = arr;       
    // }

    static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
        if (start >= end)
            return;
        int len = end - start, mid = (len >> 1) + start;
        int start1 = start, end1 = mid;
        int start2 = mid + 1, end2 = end;
        merge_sort_recursive(arr, result, start1, end1);
        merge_sort_recursive(arr, result, start2, end2);
        int k = start;
        while (start1 <= end1 && start2 <= end2)
            result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
        while (start1 <= end1)
            result[k++] = arr[start1++];
        while (start2 <= end2)
            result[k++] = arr[start2++];
        for (k = start; k <= end; k++)
            arr[k] = result[k];
    }

    public static void merge_sort(int[] arr) {
        int len = arr.length;
        int[] result = new int[len];
        merge_sort_recursive(arr, result, 0, len - 1);
    }
}